#include <stdio.h>
#include <stdlib.h>

typedef struct Queen{
    int x;
    int y;
}Queen;

typedef struct ListNode{
    Queen q;
    struct ListNode *Next;
    struct ListNode *Last;
}ListNode;

typedef struct List {
    struct ListNode *header;
    struct ListNode *trailer;
    int _size;
}List;

void CreateList(List *l);
void InsertList(List *l,Queen e);
Queen PopList(List *l);
void InsertBefore(int i,Queen e,List *l);

void CreateList(List *l){
    l->_size=0;
    l->header= (ListNode*)malloc(sizeof(ListNode));
    l->trailer=(ListNode*)malloc(sizeof(ListNode));
    l->header->Next=l->trailer;
    l->header->Last=NULL;
    l->trailer->Last=l->header;
    l->trailer->Next=NULL;
}

void InsertList(List *l,Queen e){
    ListNode *np=(ListNode*)malloc(sizeof(ListNode));
    np->q.x=e.x;
    np->q.y=e.y;
    np->Next=l->trailer;
    np->Last=l->trailer->Last;
    l->trailer->Last->Next=np;
    l->trailer->Last=np;
    l->_size++;
}

void InsertBefore(int i,Queen e,List *l){
    int j;
    ListNode *p=l->header->Next;
    for(j=0;j<i;j++){
        p=p->Next;
    }
    ListNode *np=(ListNode*)malloc(sizeof(ListNode));
    np->q.x=e.x;
    np->q.y=e.y;
    np->Next=p;
    np->Last=p->Last;
    p->Last->Next=np;
    p->Last=np;
    l->_size++;
}

void PushList(List *l,Queen e){
    ListNode *np=(ListNode*)malloc(sizeof(ListNode));
    np->q.x=e.x;
    np->q.y=e.y;
    np->Last=l->header;
    np->Next=l->header->Next;
    np->Next->Last=np;
    l->header->Next=np;
    l->_size++;
}

Queen PopList(List *l){
    ListNode *now=l->header->Next;
    Queen old=now->q;
    now->Next->Last=now->Last;
    l->header->Next=now->Next;
    free(now);
    l->_size--;
    return old;
}

int placeQ(int N){
    int solution_n = 0;
    int i;
    List solution;
    CreateList(&solution);
    Queen q;
    q.x=0;
    q.y=0;
    int *xarray=(int*)calloc(N,sizeof(int));
    int *yarray=(int*)calloc(N,sizeof(int));
    int *sumarray=(int*)calloc(2*N,sizeof(int));
    int *diffarray=(int*)calloc(2*N,sizeof(int));
    for(i=0;i<N;i++){
        xarray[i]=yarray[i]=0;
    }
    for(i=0;i<N*2;i++){
        sumarray[i]=diffarray[i]=0;
    }
    do{
        if(N<=solution._size ||N<=q.y) {
            Queen tmp = PopList(&solution);
            q.x = tmp.x;
            q.y = tmp.y;
            xarray[q.x]=0;
            yarray[q.y]=0;
            sumarray[q.x+q.y]=0;
            diffarray[q.x-q.y+N]=0;
            q.y++;
        }
        else {
            while ((q.y < N) && ((xarray[q.x] == 1) || (yarray[q.y] == 1) || \
            (sumarray[q.x + q.y] == 1) || (diffarray[q.x - q.y + N]) == 1)) {
                q.y++;
            }
            if (N > q.y) {
                PushList(&solution, q);
                xarray[q.x] = 1;
                yarray[q.y] = 1;
                sumarray[q.x + q.y] = 1;
                diffarray[q.x - q.y + N] = 1;
                if (N <= solution._size) {
                    solution_n++;
                }
                q.x++;
                q.y = 0;
            }
        }
    }
    while((q.x>0)||(q.y<N));
    return solution_n;
}

int main() {
    int num;
    scanf("%d",&num);
    printf("%d",placeQ(num));
    return 0;
}